package demo1;

public class Sort {
    //快速排序
    private int fundPoint(int[] array, int start, int end){
        int key = array[start];
        while(start < end){
            while(start < end && key <= array[end]){
                end--;
            }
            array[start] = array[end];
            while(start < end && array[start] <= key){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = key;
        return start;
    }
    //三数取中优化
    private int fundMidIndex(int[] array, int left, int right){
        int mid = (left + right) / 2;
        if(array[left] > array[right]){
            if(array[mid] > array[left]) {
                return left;
            }else if(array[mid] < array[right]) {
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else{
                return mid;
            }
        }
    }
    private void quick(int[] array, int left, int right){
        if(left >= right){
            return;
        }
        int midIndex = fundMidIndex(array, left, right);
        swap(array, left, midIndex);
        //找基准
        int point = fundPoint(array, left, right);
        quick(array, left, point - 1);
        quick(array, point + 1, right);
    }
    public void quickSort(int[] array){
        quick(array, 0, array.length - 1);
    }
    private void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
